import java.util.Scanner;

/**
 * Description:
 * Date: 2025-11-13
 * Time: 9:20
 */
public class BinaryTree {
    static class TreeNode{
        public char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //先创建一棵树
    public TreeNode creatTree() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.right = nodeG;
        nodeE.right = nodeF;

        return nodeA;
    }

    //翻转二叉树  https://leetcode.cn/problems/invert-binary-tree/description/
    public TreeNode invertTree(TreeNode root) {
        //递归结束条件
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        //从后面。翻转每一个小的二叉树，最后翻转大的二叉树结束
        TreeNode tmp = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = tmp;

        //将自己整个返回
        return root;

    }

    public static boolean isSymmetry(TreeNode p, TreeNode q) {
        //判断当前节点是否对称
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        //先判定null，为null则直接返回
        if (p == null && q == null) {
            return true;
        }
        //上述代码避免了左右节点为空引用的现象
        if (p.val != q.val) {
            return false;
        }
        return isSymmetry(p.left,q.right) && isSymmetry(p.right,q.left);
    }

    //对称二叉树  https://leetcode.cn/problems/symmetric-tree/description/
    public boolean isSymmetric(TreeNode root) {
        //为空，什么都没有即对称
        if (root == null) {
            return true;
        }
        //判断最开始的根节点的左子树和右子树是否对称
        return isSymmetry(root.left, root.right);
    }

    public static int getHeight1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight1(root.left),getHeight1(root.right)) + 1;
    }

    //平衡二叉树  https://leetcode.cn/problems/balanced-binary-tree/
    public boolean isBalanced1(TreeNode root) {
        if (root == null) {
            return true;
        }
        //先进行判断  再往下递归 (从上到下)
        //保证当前这个节点返回的是false，不会被之后的结果覆盖
        if (Math.abs(getHeight1(root.left) - getHeight1(root.right)) > 1) {
            return false;
        }
        return isBalanced1(root.left) && isBalanced1(root.right);
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        //从下到上进行判断，主体函数只递归一次
        int lfetTree = getHeight(root.left);
        int rightTree = getHeight(root.right);

        if(lfetTree == -1 || rightTree == -1) {
            return false;
        }
        if (Math.abs(lfetTree - rightTree) > 1) {
            return false;
        }
        return true;
    }

    public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lfetTree = getHeight(root.left);
        if (lfetTree == -1) {
            return -1;
        }
        int rightTree = getHeight(root.right);
        if (rightTree == -1) {
            return -1;
        }

        if (Math.abs(lfetTree - rightTree) > 1) {
            return -1;
        }
        return Math.max(lfetTree,rightTree) + 1;
    }


    //二叉搜索树与双向链表  https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&ru=/exam/oj
    //定义一个全局变量记录前驱
    TreeNode prev = null;
    public  void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        //利用前驱变量改变节点的指向
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;
        inorder(root.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        //存在0个节点的树
        if (pRootOfTree == null) {
            return null;
        }
        //进行排序
        inorder(pRootOfTree);
        TreeNode head = pRootOfTree;
        //寻找头节点
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    //二叉树的遍历和构建  https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            BinaryTree a = new BinaryTree();
            TreeNode root = a.creatTree(str);
            a.inorderTree(root);
        }
    }

    //i遍历字符串，需要不受递归影响
    public int i = 0;
    public TreeNode creatTree(String str) {
        //int i = 0;
        char ch = str.charAt(i);
        TreeNode root = null;
        //判断当前字是否为空格进行操作
        if (ch != '#') {
            //创建当前对象完就需要进行i++
            root = new TreeNode(ch);
            i++;
            //创建当前节点的左子树的对象，递归回来时结构设置为前序遍历并且进行连接
            root.left = creatTree(str);
            //创建当前节点的右子树对象
            root.right = creatTree(str);
            //先创建，在连接
        }else {
            //当前字符为空格，不操作
            i++;
        }
        return root;
    }

    public void inorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTree(root.left);
        System.out.print(root.val + " ");
        inorderTree(root.right);
    }






}
